const arr = [2, 8, 5, 1, 3, 2, 0]

// function quick_sort(arr) {
//   const len = arr.length
//   if (len <= 1) return arr
//   let l = []
//   let r = []
//   const mid = arr.splice(len >> 1, 1)[0]
//   for (x of arr) {
//     if (x > mid) r.push(x)
//     else l.push(x)  
//   } 
//   return [...quick_sort(l), mid, ...quick_sort(r)]
// }

// function merge_sort(arr) {
//   const len = arr.length
//   if (len <= 1) return arr
//   const mid = len >> 1
//   let l = merge_sort(arr.slice(0, mid))
//   let r = merge_sort(arr.slice(mid))
//   arr = mergeArr(l, r)
//   return arr
// }

// function mergeArr(l, r) {
  // let i = 0, j = 0
  // const len1 = l.length
  // const len2 = r.length
  // let res = []
  // while (i < len1 && j < len2) {
  //   if (l[i] < r[j]) {
  //     res.push(l[i])
  //     i++
  //   } else {
  //     res.push(r[j])
  //     j++
  //   }
  // }
  // if (i < len1) {
  //   res = res.concat(l.slice(i))
  // } else {
  //   res = res.concat(r.slice(j))
  // }
  // return res
// }

// console.log(quick_sort(arr));
// function merge_sort(arr) {
//   const len = arr.length
//   if (len <= 1) return arr
//   const mid = len >> 1
//   let l = merge_sort(arr.slice(0, mid))
//   let r = merge_sort(arr.slice(mid))
//   arr = merge(l, r)
//   return arr
// }

// function merge(l, r) {
//   let i = 0, j = 0
//   const len1 = l.length
//   const len2 = r.length
//   let res = []
//   while (i < len1 && j < len2) {
//     if (l[i] < r[j]) {
//       res.push(l[i])
//       i++
//     } else {
//       res.push(r[j])
//       j++
//     }
//   }
//   if (i < len1) {
//     res = res.concat(l.slice(i))
//   } else {
//     res = res.concat(r.slice(j))
//   }
//   return res
// }
// console.log(merge_sort(arr));

function merge_sort(arr) {
  const len = arr.length
  if (len <= 1) return arr
  const mid = len >> 1
  let l = []
  let r = []
  l = merge_sort(arr.slice(0, mid))
  r = merge_sort(arr.slice(mid))
  arr = merge(l, r)
  return arr
}

function merge(l, r) {
  let i = 0, j = 0
  let n = l.length, m = r.length
  let ans = []
  while (i < n && j < m) {
    if (l[i] < r[j]) {
      ans.push(l[i])
      i++
    } else {
      ans.push(r[j])
      j++
    }
  }
  if (i < n) ans = ans.concat(l.slice(i))
  else ans = ans.concat(r.slice(j))
  return ans  
}

console.log(merge_sort(arr));
